﻿//https://leetcode.cn/problems/replace-words/?envType=problem-list-v2&envId=hash-table

class Solution {
public:
    vector<string_view> splice(string& sentence, char ch)
    {
        int pos = 0;
        int begin = 0;
        string_view s(sentence);
        vector<string_view> ret;
        while (pos < s.size())
        {
            while (pos < s.size() && s[pos] == ch)
            {
                pos++;
            }
            begin = pos;
            while (pos < s.size() && s[pos] != ch)
            {
                pos++;
            }
            if (begin < s.size())
            {
                ret.emplace_back(s.substr(begin, pos - begin));
            }
        }
        return ret;
    }
    string replaceWords(vector<string>& dictionary, string sentence)
    {
        unordered_set<string_view>  dictionarySet;
        for (auto& e : dictionary)
        {
            dictionarySet.emplace(e);
        }

        vector<string_view> words = splice(sentence, ' ');
        for (auto& e : words)
        {
            for (int i = 0; i < e.size(); i++)
            {
                if (dictionarySet.count(e.substr(0, i + 1)))
                {
                    e = e.substr(0, i + 1);
                    break;
                }
            }
        }

        string ret;
        for (int i = 0; i < words.size() - 1; i++)
        {
            ret += words[i];
            ret += " ";
        }
        ret += words.back();
        return ret;
    }
};
